package addressBook;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Stack;
import java.util.function.Consumer;

/**
 * Init this class should store a tree to a linked list.
 * and we can use hasNext() and next() to invoke it.
 * * Default is in-order(because in order traversal can get a ordered and increasing list)
 * @author Jarvan
 * @version 1.0
 * @create 2020/11/13 9:14
 */
public class TreeIterator<E> implements Iterator<E> {
    private BaseBinaryTree<E> tree;
    /**   Store the in-order(pre-order ,post order) sequence of the binary search tree. */
    public LinkedList<TreeNode<E>> list;
    /**
     * 1 is preOrder ,2 is inOrder, 3 is postOrder.
     */
    private int traverseMethod;
    /**
     * Element index.
     */
    int index;

    public TreeIterator(BaseBinaryTree<E> tree) {
        //Default is in-order(because in order traversal can get a ordered and increasing list)
        this(tree,2);
    }

    public TreeIterator(BaseBinaryTree<E> tree, int traverseMethod) {
        list = new LinkedList<>();
        this.tree = tree;
        this.traverseMethod = traverseMethod;
        this.index = -1;
        // init linked list.
        traverse();

    }

    private void traverse(){
        if (traverseMethod == 1){
            //pre order
            preOrder(tree.root);

        }else if (traverseMethod == 3){
            //post order.
            postOrder(tree.root);
        }else {
            //in order.
            inOrder(tree.root);
        }
    }

    /**
     * preOrder no recuesion.
     * @param root root tree node.
     */
    private void preOrder(TreeNode<E> root){
        Stack<TreeNode<E>> treeNodeStack = new Stack<>();
        while (root != null || !treeNodeStack.isEmpty()) {
            while (root != null) {
                //store node to list.
                list.add(root);
                //store node to  stack.(for traversal)
                treeNodeStack.push(root);
                root = root.left;
            }
            if (!treeNodeStack.isEmpty()) {
                root = treeNodeStack.pop();
                root = root.right;
            }
        }
    }
    private void inOrder(TreeNode<E> root){
        Stack<TreeNode<E>> treeNodes = new Stack<>();
        while (root!=null || !treeNodes.isEmpty()){
            while (root != null) {
                //store node to  stack.(for traversal)
                //temporary store the node , so I can back the node again.
                treeNodes.push(root);
                //point to left (always)
                root = root.left;
            }
            //if treeNodes is  not empty we can pop the node and ,traversal the node right node.
            if (!treeNodes.isEmpty()){
                TreeNode<E> popNode = treeNodes.pop();
                //store node to list.
                list.add(popNode);
                //traverse next node.
                root = popNode.right;
            }
        }
    }

    /**
     * Traversal binary tree by postOrder.
     * Get element value while a node's right tree and left tree all is null.
     * @param root root.
     */
    private void postOrder(TreeNode<E> root){
        Stack<TreeNode<E>> treeNodesStack = new Stack<>();
        //visited pointer to the node that has output to list.
        TreeNode<E> visited =root;
        while (root != null || !treeNodesStack.isEmpty()){
            while (root != null) {
                //temporary store root in stack.
                treeNodesStack.push(root);
                root = root.left;
            }
            //[important] there we just peek the stack top not pop it.
            root = treeNodesStack.peek();
            //if node(root).right is null or the right is visited
            // (we  out put it and let the visited = node)
            // and then ,we pop the stack top to invoke the up level node.
            if (root.right == null || root.right == visited){
                list.add(root);
                visited = root;
                root = treeNodesStack.pop();
                //to avoid push(root) endless loop.
                root = null;
            }else {
                //if right not nll and is not visited , we let root pointer to it right subtree
                root = root.right;
            }
        }
    }

    /**
     * Returns {@code true} if the iteration has more elements.
     * (In other words, returns {@code true} if {@link #next} would
     * return an element rather than throwing an exception.)
     *
     * @return {@code true} if the iteration has more elements
     */
    @Override
    public boolean hasNext() {
        return !list.isEmpty() && index < (list.size() - 1);
    }

    /**
     * Returns the next element in the iteration.
     *
     * @return the next element in the iteration
     * @throws NoSuchElementException if the iteration has no more elements
     */
    @Override
    public E next() {
        index ++;
        return list.get(index).element;
    }

    /**
     * Removes from the underlying collection the last element returned
     * by this iterator (optional operation).  This method can be called
     * only once per call to {@link #next}.  The behavior of an iterator
     * is unspecified if the underlying collection is modified while the
     * iteration is in progress in any way other than by calling this
     * method.
     * more info of remove(https://howtodoinjava.com/java/collections/java-iterator/)
     *
     *
     * @throws UnsupportedOperationException if the {@code remove}
     *                                       operation is not supported by this iterator
     * @throws IllegalStateException         if the {@code next} method has not
     *                                       yet been called, or the {@code remove} method has already
     *                                       been called after the last call to the {@code next}
     *                                       method
     * @implSpec The default implementation throws an instance of
     * {@link UnsupportedOperationException} and performs no other action.
     */
    @Override
    public void remove() {
        list.remove(index);
    }

    /**
     * Performs the given action for each remaining element until all elements
     * have been processed or the action throws an exception.  Actions are
     * performed in the order of iteration, if that order is specified.
     * Exceptions thrown by the action are relayed to the caller.
     *
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @implSpec <p>The default implementation behaves as if:
     * <pre>{@code
     *     while (hasNext())
     *         action.accept(next());
     * }</pre>
     * @since 1.8
     */
    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        while (hasNext()) {
            action.accept(next());
        }
    }
    /**
     * Set  traverseMethod = 1;
     */
    public void setPreOrder(){
        traverseMethod = 1;
    }

    /**
     * Set  traverseMethod = 2
     */
    public void setInOrder(){
        traverseMethod = 2;
    }

    /**
     * Set  traverseMethod = 3
     */
    public void setPostOrder(){
        traverseMethod = 3;
    }
}
